package leetcode

// https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/
func shipWithinDays(weights []int, days int) int {
	total, n := 0, len(weights)
	for i := 0; i < n; i++ {
		total += weights[i]
	}
	left, right := 0, total
	for mid := (left + right) / 2; left <= right; mid = (left + right) / 2 {
		if check(weights, days, mid) {
			right = mid - 1
		} else {
			left = left + 1
		}
	}
	return left
}

func check(weights []int, days, capacity int) bool {
	preday, count := 0, 0
	for _, w := range weights {
		if w > capacity {
			return false
		}
		if count+w <= capacity {
			count += w
		} else {
			preday++
			count = w
		}
	}
	return preday+1 <= days
}
